googologywikiaorg-20200223-history
Order theory
Order theory is the study of the transitive order relation, and laws for determining the order of mathematical objects for which order is defined, such as real numbers. on Wikipedia One objective of googology is discovering the order between different large numbers, otherwise a largest number cannot be established from a set of large numbers. Basic rules of order for arithmetic The basic rules of order for natural numbers can be derived for the Peano arithmetic. The successor function is defined so that it's output is always greater than it's input. From this definition and the rest included in Peano arithmetic, all natural numbers can be ordered. While it is easy to compare the order of small numbers just using iteration of the successor function, it is much harder to compare larger numbers. For this, further rules of order can be derived from the properties of arithmetic. Rules of addition # A + 0 = A # If A is positive, than A + B is greater than B. # If A is negative, than A + B is less than B. # If A is greater than B, than A + C is greater than B + C. # If A is less than B, than A + C is less than B + C. Rules of multiplication # A * 1 = A # A * 0 = 0 # If A is positive and B is positive, than A * B is positive. # If A is positive and B is negative, than A * B is negative. # If A is negative and B is negative, than A * B is positive. # If the absolute value of A is greater than one, than the absolute value of A * B is greater than the absolute value of B. # If the absolute value of A is less than one, than the absolute value of A * B is less than the absolute value of B. # If the absolute value of A is greater than B, than the absolute value of A * C is greater than the absolute value of B * C. # If the absolute value of A is less than B, than the absolute value of A * C is less than the absolute value of B * C. Positional notation As all natural numbers are positive, the rules are much simpler over them. The fact all natural numbers except zero and one are greater than one further simplifies their use. Using just these rules order can easily be determined between any two numbers which can be represented using positional notation. The algorithm for comparing order is first to compare the number of symbols. The number that requires the longer string to represent it is larger. This is because the least number with the greater amount of digits is one greater than the greatest number with the lesser amount of digits, so only the transitive property of order is needed to establish order in that case. When two numbers require the same amount of digits, the one with the larger initial digit is larger. This follows from a combination of the 4th rule of addition and the 8th rule of multiplication. The 4th rule allows the rest of the digits to be ignored as they are always smaller than the difference between values represented by the foremost digit, and a larger digit results in a larger front based on the 8th rule. Finally, if the foremost digits are the same, the numbers represented by the rest of the string can be compared to determine which number is larger. This again follows from the 4th rule of addition as ultimately position notation represents a sum. Larger numbers need a more generalized application of order theory though so more specific order laws can found with which to compare large numbers. Monotonic functions A monotonic function is function with the property that if one input value is greater than another, then it's output is greater or equal to the other's output. A strictly monotonic function is a monotonic function where the output must be greater. Bounding A function bounds another function when for all input values greater than a certain number, the output values in the second function are greater than the first. By establishing such a number for two functions, finding an index greater than that number, and showing that the value of the bounding function at that index is the lower bound for one number, while the upper bound for another number is the value at the index for the bounded function, it can be established that one number is greater than another. Any exponential function bounds any power function. For numbers which are too large to expressed in positional notation, but are still small enough to be expressed using a combination of exponentiation and positional notation, this law can be used to order them. It can be proven that some uncomputable functions bound all computable functions. This is very useful for establishing the order of extremely large numbers. See also * Ordinal * List of functions Sources Category:Set theory